package algorithm.状态压缩的动态规划;
/*
* 有N个城市，任何两个城市之间的都有距离，任何一座城市到自己的距离都为0
所有点到点的距离都存在一个N*N的二维数组matrix里，也就是整张图由邻接矩阵表示
现要求一旅行商从k城市出发必须经过每一个城市且只在一个城市逗留一次，最后回到出发的k城
参数给定一个matrix，给定k。返回总距离最短的路的距离
* */
public class TSP {

    public static int tsp1(int[][] matrix){
        int N = matrix.length;
        int length = (1 << N) - 1;
        int[][] dp = new int[length + 1][N];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        int start = 0;
        int status = 1;
        return process(status, start, dp, matrix);
    }

    public static int process(int status, int start, int[][] dp, int [][] matrix){
        if(dp[status][start] != -1){
            return dp[status][start];
        }

        int N = matrix.length;

        if(status == (1 << N) - 1){
            dp[status][start] = matrix[start][0];
            return matrix[start][0];
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            if((status & (1 << i)) == 0){
                min = Math.min(min, matrix[start][i] + process(status | (1 << i), i, dp, matrix));
            }
        }

        dp[status][start] = min;

        return min;
    }

    public static int t4(int[][] matrix) {
        int N = matrix.length; // 0...N-1
        int statusNums = 1 << N;
        int[][] dp = new int[statusNums][N];

        for (int status = 0; status < statusNums; status++) {
            for (int start = 0; start < N; start++) {
                if ((status & (1 << start)) != 0) {
                    if (status == (status & (~status + 1))) {
                        dp[status][start] = matrix[start][0];
                    } else {
                        int min = Integer.MAX_VALUE;
                        // start 城市在status里去掉之后，的状态
                        int preStatus = status & (~(1 << start));
                        // start -> i
                        for (int i = 0; i < N; i++) {
                            if ((preStatus & (1 << i)) != 0) {
                                int cur = matrix[start][i] + dp[preStatus][i];
                                min = Math.min(min, cur);
                            }
                        }
                        dp[status][start] = min;
                    }
                }
            }
        }
        return dp[statusNums - 1][0];
    }

    public static int[][] generateGraph(int maxSize, int maxValue) {
        int len = (int) (Math.random() * maxSize) + 1;
        int[][] matrix = new int[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                matrix[i][j] = (int) (Math.random() * maxValue) + 1;
            }
        }
        for (int i = 0; i < len; i++) {
            matrix[i][i] = 0;
        }
        return matrix;
    }

    public static void main(String[] args) {
        int len = 10;
        int value = 100;
        System.out.println("功能测试开始");
        for (int i = 0; i < 20000; i++) {
            int[][] matrix = generateGraph(len, value);
            int origin = (int) (Math.random() * matrix.length);
            int ans1 = tsp1(matrix);
            int ans2 = t4(matrix);
            if (ans1 != ans2) {
                System.out.println("fuck");
            }
        }
        System.out.println("功能测试结束");

        len = 22;
        System.out.println("性能测试开始，数据规模 : " + len);
        int[][] matrix = new int[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                matrix[i][j] = (int) (Math.random() * value) + 1;
            }
        }
        for (int i = 0; i < len; i++) {
            matrix[i][i] = 0;
        }
        long start;
        long end;
        start = System.currentTimeMillis();
        t4(matrix);
        end = System.currentTimeMillis();
        System.out.println("运行时间 : " + (end - start) + " 毫秒");
        System.out.println("性能测试结束");

    }

}
